/**
 * MaxIntHeap.java
 *
 *
 * Created: Mon Jul 8 13:07:49 2002
 *
 * @author Scott Sanner - intern
 * @version 1.0
 */
package mahmoud.utils;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

import org.apache.commons.collections.buffer.PriorityBuffer;

//import java.util.Arrays;

/**
 * A heap implementation for priority queue type operations.
 * Assumes (-1) is an invalid value.
 */
public class MinHeap<T> 
{

	// Note, for arithmetic efficiency and clarity, a[1]
	// is the first.  Actual array size is always at least
	// 1 + sz.
	public Comparable<T>[] a;                      // array
	private int   sz = 0;                 // num elements

	public static int MAX_SZ = 10; // default heap size
	/**
	 * Build a priority queue from scratch
	 */
	public MinHeap() 
	{
		a  = new Comparable[MAX_SZ];
		sz = 0;
	}
	public MinHeap(int size)
	{
		MAX_SZ = size;
		a = new Comparable[size+1];
		sz= 0;
	}

	/**
	 * Build a priority queue from an integer array
	 */ 
	//	public MinHeap(Comparable<T>[] val, int size) 
	//	{
	//		a = new Comparable[size + 1];
	//
	//		// a[1] is the first element, a[0] is unused
	//		System.arraycopy(val, 0, a, 1, size);
	//		sz = size;
	//		buildHeap();
	//	}

	/**
	 * Turn the array into a heap
	 */
	public void buildHeap() 
	{
		for (int i = sz >> 1; i >= 1; i--) 
		{
			heapify(i);
		}
	}

	/**
	 * Heapify the subtree rooted at node i, and recurse the swapped
	 * subtree
	 */
	public void heapify(int i) 
	{
		int l, r, largest;
		boolean cont = true;
		while (cont) 
		{
			l = 2 * i; // The left subnode
			r = l + 1; // The right subnode
			if (l <= sz && a[l].compareTo((T) a[i]) < 0) 
			{
				largest = l;
			}
			else 
			{
				largest = i;
			}	    
			if (r <= sz && a[r].compareTo( (T) a[largest])<0) 
			{
				largest = r;
			}
			if (largest != i) 
			{
				Comparable<T> temp = a[i];
				a[i] = a[largest];
				a[largest] = temp;
				i = largest; // heapify(largest)
			} 
			else 
			{
				cont = false; // No need to recurse
			}
		}
	}

	/**
	 * Insert an element into the queue
	 */
	public void add(Comparable<T> key) 
	{
		if(!this.isFull())
			addkey(key);//add key
		else if (this.isFull())
		{
			if(this.peek().compareTo((T)key)< 0 )
			{
				this.poll();
				addkey(key);//add key
			}
		}
	}
	private void addkey(Comparable<T> key)
	{
		int cld = ++sz;
		
		int parent;
		while (cld > 1 && a[parent = (cld >> 1)].compareTo((T) key)>0) 
		{
			a[cld] = a[parent];
			cld = parent;
		}
		a[cld] = key;
	}

	/**
	 * Remove the max element from the queue
	 */
	public Comparable<T> poll() 
	{
		if (sz == 0) 
		{
			return (null);
		}
		Comparable<T> min = a[1];
		a[1] = a[sz];
		sz--;
		heapify(1);
		return min;
	}

	/**
	 * Check the max element in the queue but do not remove
	 */
	public Comparable<T> peek() 
	{
		if (sz > 0) 
		{
			return a[1];
		} 
		else 
		{
			return (null);
		}
	}

	/**
	 * Is heap empty?
	 */
	public String toString()
	{
		MinHeap<T> copy = this.clone();
		StringBuffer sb = new StringBuffer();
		String output = "";
		int x = MAX_SZ;
		for (int i =0 ; i < MAX_SZ ; i++)
			output = String.format("%d \t %s\n%s",x-i,copy.poll().toString(),output);
//			sb.append (i+".\t"+poll().toString()+"\n" );
		return output;
	}
	public boolean isEmpty() 
	{
		return (sz == 0);
	}
	public boolean isFull()
	{
		return (sz >= MAX_SZ);
	}
	public int size()
	{
		return sz;
	}
//	public boolean containsResult(R element)
//	{
//		for(Comparable<T> item : a)
//		{
//			if(item == null)
//				continue;
//			if(item.compareTo((T) element)==0)
//				return true;
//		}
//		return false;
//	}
//	public int matchesResult(MinHeap<T> otherH)
//	{
//		MinHeap<T> copy = this.clone();
//		int result =0;
//		while(!copy.isEmpty())
//		{
//			if(otherH.containsResult(copy.poll()))
//					result++;
//		}
//		return result;
//	}

	/**
	 * Print the current heap
	 */
	public String printHeap() 
	{
		StringBuffer sb1 = new StringBuffer();
		StringBuffer sb2 = new StringBuffer();
		for (int i = 1; i <= sz; i++)
		{
			sb1.append(i + "\t");
			sb2.append("["+a[i]+"]" + "\t");
		}
		if(isFull())
			sb1.append("\t HEAP IS FULL");
		return sb1.toString() + "\n" + sb2.toString();
	}
	public MinHeap<T> clone()
	{
		MinHeap<T> cloned = new MinHeap<T>(MAX_SZ);
		cloned.sz = sz;
		cloned.a = a.clone();
		return cloned;
	}

	/**
	 * Testing method
	 */
	public static void main(String args[]) 
	{
		int top =20;
		int total = 10000;
		int maxRand = 200000;
		boolean testFailed = false;
		ArrayList<Integer> fromArrayList = new ArrayList<Integer>();
		ArrayList<Integer> fromHeap = new ArrayList<Integer>();
		Random gen = new Random();
		
		for(int i = 0 ; i<total ; i++)
		{
			fromArrayList.add(gen.nextInt(maxRand));
		}
		
		MinHeap<Integer> h = new MinHeap<Integer>(top);
		for (Integer x : fromArrayList)
		{
				h.add(x);
				System.out.println("Heap size: "+ h.size());
		}
//		System.exit(0);
		//save the heap-selected top results to an arraylist 
		while (!h.isEmpty())
		{
			 fromHeap.add((Integer) h.poll());
		}
		
		Collections.sort(fromArrayList,Collections.reverseOrder());
		ArrayList<Integer>  al = new ArrayList<Integer>( fromArrayList.subList(0, top));
		Collections.sort(al);
		for (int j = 0; j< top ; j++)
		{
//			System.out.println("AL : "+al.get(j)+ "\t From Heap: "+fromHeap.get(j));
			if(!fromHeap.get(j).equals(al.get(j))  )
			{
				System.out.println("AT Index : "+j+" AL : "+al.get(j)+ "\t From Heap: "+fromHeap.get(j));
				testFailed= true;
			}
		}
		if(testFailed)
			System.out.println("The HEap didnt work as expected");
		else
			System.out.println("Test Successfull..!");
		
	}
}
